package com.haidechizi.sort;

import java.util.Arrays;

/**
 * @author: wangdejun
 * @create: 2020-04-14 10:23
 * 时间复杂度：O(logn)
 * 空间复杂度：O(logn)
 **/
public class MergeSort {

    public static void main(String[] args) {
        int[] array = new int[]{9, 3, 17, 8, 5, 6, 7, 3, 5, 6, 2, 1, 33};
//        int[] array = new int[]{3, 6, 9, 22, 4, 7, 15};
//        merge(array, 0, 3, array.length - 1);
        mergeSort(array, 0, array.length - 1);
        System.out.println(Arrays.toString(array));

    }

    public static void mergeSort(int[] array, int start, int end) {
        if (start >= end) {
            return;
        }
        int middle = (end + start) / 2;
        mergeSort(array, start, middle);
        mergeSort(array, middle + 1, end);
        merge(array, start, middle, end);
    }

    public static void merge(int[] array, int start, int middle, int end) {
        int[] tempArr = new int[end - start + 1];
        int low = start;
        int high = middle + 1;
        int index = 0;
        while (low <= middle && high <= end) {
            while (low <= middle && array[low] <= array[high]) {
                tempArr[index] = array[low];
                index++;
                low++;
            }
            while (high <= end && array[high] < array[low]) {
                tempArr[index] = array[high];
                index++;
                high++;
            }
        }
        while (low <= middle) {
            tempArr[index] = array[low];
            index++;
            low++;
        }

        while (high <= end) {
            tempArr[index] = array[high];
            index++;
            high++;
        }
        for (int i = 0; i < tempArr.length; i++) {
            array[start + i] = tempArr[i];
        }
    }
}
